算法

您所在的位置:网站首页 avant de partir原文 算法

算法

2023-11-10 07:06| 来源: 网络整理| 查看: 265

文章目录 简介1. 算法原理2. 算法流程2.1 初始化种群2.2 变异2.3 交叉2.4 选择 3. 算法代码3.1 伪代码3.2 matlab 4. 参数控制[^1]4.1 参数说明4.2 参数选择 5. 改进方法[^1]5.1 自适应变异算子

简介

    差分进化算法(Differential Evolution,DE)由Storn和Price于1995年首次提出。主要用于求解实数优化问题。该算法是一类基于群体的自适应全局优化算法,属于演化算法的一种,由于其具有结构简单、容易实现、收敛快速、鲁棒性强等特点,因而被广泛应用在数据挖掘、模式识别、数字滤波器设计、人工神经网络、电磁学等各个领域。1996年在日本名古屋举行的第一届国际演化计算(ICEO)竞赛中,差分进化算法被证明是速度最快的进化算法。

1. 算法原理

    DE算法通过采用浮点矢量进行编码生成种群个体。在DE算法寻优的过程中,首先,从父代个体间选择两个个体进行向量做差生成差分矢量;其次,选择另外一个个体与差分矢量求和生成实验个体;然后,对父代个体与相应的实验个体进行交叉操作,生成新的子代个体;最后在父代个体和子代个体之间进行选择操作,将符合要求的个体保存到下一代群体中去。

2. 算法流程

假设优化模型如下: min ⁡ f ( x 1 , x 2 , ⋯   , x D )  s.t  x j L ⩽ x j ⩽ x j U , j = 1 , 2 , ⋯   , D \begin{array}{l}{\min f\left(x_{1}, x_{2}, \cdots, x_{D}\right)} \\ {\text { s.t } \quad x_{j}^{L} \leqslant x_{j} \leqslant x_{j}^{U}, j=1,2, \cdots, D}\end{array} minf(x1​,x2​,⋯,xD​) s.t xjL​⩽xj​⩽xjU​,j=1,2,⋯,D​ w h e r e where where,D是解空间的维度, x j L x_{j}^{L} xjL​、 x j U x_{j}^{U} xjU​分别表示第j个分量 x j x_{j} xj​取值范围的上界和下界。

2.1 初始化种群

初始化种群为: { x i ( 0 ) ∣ x j , i L ⩽ x j , i ( 0 ) ⩽ x j , i v , i = 1 , 2 , ⋯   , N P ; j = 1 , 2 , ⋯   , D } \left\{x_{i}(0) | x_{j, i}^{L} \leqslant x_{j, i}(0)\leqslant x_{j, i}^{v}, i=1,2, \cdots, N P ; j=1,2, \cdots, D\right\} {xi​(0)∣xj,iL​⩽xj,i​(0)⩽xj,iv​,i=1,2,⋯,NP;j=1,2,⋯,D} 由下式随机生成各种群个体: x j , i ( 0 ) = x j , i L + r a n d ( 0 , 1 ) ⋅ ( x j , i U − x j , i L ) x_{j, i}(0)=x_{j, i}^{L}+{rand}(0,1) \cdot\left(x_{j, i}^{U}-x_{j, i}^{L}\right) xj,i​(0)=xj,iL​+rand(0,1)⋅(xj,iU​−xj,iL​) w h e r e where where, x i ( 0 ) x_{i}(0) xi​(0)表示种群中第0代的第i个个体, x j , i ( 0 ) x_{j, i}(0) xj,i​(0)表示第0代的第i个个体的第j个基因。NP表示种群大小, r a n d ( 0 , 1 ) {rand}(0,1) rand(0,1)表示在(0,1)区间均匀分布的随机数。

在这里插入图片描述

2.2 变异

    差分进化算法与遗传算法最显著的区别在于DE的个体变异是通过差分策略实现的。

常用的差分策略如下: ν i ( g + 1 ) = x i 1 ( g ) + F ⋅ ( x i ( g ) − x i j ( g ) ) i ≠ r 1 ≠ r 2 ≠ r 3 \begin{array}{c}{\nu_{i}(g+1)=x_{i_{1}}(g)+F \cdot\left(x_{i}(g)-x_{i j}(g)\right)} \\ {i \neq r_{1} \neq r_{2} \neq r_{3}}\end{array} νi​(g+1)=xi1​​(g)+F⋅(xi​(g)−xij​(g))i​=r1​​=r2​​=r3​​

w h e r e where where, F {F} F为缩放因子, x i ( g ) x_{i}(g) xi​(g)为第g代种群中第i个个体。

即通过随机选取种群中两个不同的个体,将其向量差缩放后与待变异个体进行向量合成。

    在进化过程中,必须保证新生成的解的有效性,因此必须判断生成的解是否满足边界条件,如果不满足,则需要重新生成(生成方案与初始种群相同)。

第g代种群: { x i ( g ) ∣ x j , i L ⩽ x j , i ( g ) ⩽ x j , i v , i = 1 , 2 , ⋯   , N P ; j = 1 , 2 , ⋯   , D } \left\{x_{i}(g) | x_{j, i}^{L} \leqslant x_{j, i}(g)\leqslant x_{j, i}^{v}, i=1,2, \cdots, N P ; j=1,2, \cdots, D\right\} {xi​(g)∣xj,iL​⩽xj,i​(g)⩽xj,iv​,i=1,2,⋯,NP;j=1,2,⋯,D} 变异后的中间体:第g代种群: { x i ( g + 1 ) ∣ x j , i L ⩽ x j , i ( g + 1 ) ⩽ x j , i v , i = 1 , 2 , ⋯   , N P ; j = 1 , 2 , ⋯   , D } \left\{x_{i}(g+1) | x_{j, i}^{L} \leqslant x_{j, i}(g+1)\leqslant x_{j, i}^{v}, i=1,2, \cdots, N P ; j=1,2, \cdots, D\right\} {xi​(g+1)∣xj,iL​⩽xj,i​(g+1)⩽xj,iv​,i=1,2,⋯,NP;j=1,2,⋯,D}

在这里插入图片描述

2.3 交叉

    使用第g代种群和其变异中间体进行交叉:

u j , i ( g + 1 ) = { v j , i ( g + 1 ) ,  if  rand ⁡ ( 0 , 1 ) ⩽ C R  or  j = j rand x j , i ( g ) ,  otherwise  \begin{aligned} u_{j, i}(g+1) =\left\{\begin{array}{ll}{v_{j, i}(g+1),} & {\text { if } \operatorname{rand}(0,1) \leqslant C R \text { or } j=j_{\text {rand}}} \\ {x_{j, i}(g),} & {\text { otherwise }}\end{array}\right.\end{aligned} uj,i​(g+1)={vj,i​(g+1),xj,i​(g),​ if rand(0,1)⩽CR or j=jrand​ otherwise ​​ w h e r e where where,CR为交叉概率, j r a n d j_{rand} jrand​为[1,2,……,D]的随机整数。

在这里插入图片描述     上图为6个基因位的“染色体”或称为“个体”的交叉操作示意图。为了确保变异中间体{ v j , i ( g + 1 ) {v_{j, i}(g+1)} vj,i​(g+1)}的每个“染色体”至少有一个“基因”遗传给下一代,第一个交叉操作的基因是随机选择 v j , i ( g + 1 ) {v_{j, i}(g+1)} vj,i​(g+1)的第 j r a n d j_{rand} jrand​作为交叉后的个体 u j , i ( g + 1 ) u_{j, i}(g+1) uj,i​(g+1)第 j r a n d j_{rand} jrand​位的等位基因。后续的交叉操作则是通过交叉概率CR来选取 x i ( g ) x_{i}(g) xi​(g)还是 v i ( g + 1 ) v_{i}(g+1) vi​(g+1)的等位基因作为 u i ( g + 1 ) u_{i}(g+1) ui​(g+1)的等位基因。

在这里插入图片描述

2.4 选择

    采用贪婪算法来选择下一代种群个体: x i ( g + 1 ) = { u i ( g + 1 ) ,  if  f ( u i ( g + 1 ) ) ⩽ f ( x i ( g ) ) x i ( g ) ,  otherwise  x_{i}(g+1)=\left\{\begin{array}{ll}{u_{i}(g+1),} & {\text { if } f\left(u_{i}(g+1)\right) \leqslant f\left(x_{i}(g)\right)} \\ {x_{i}(g),} & {\text { otherwise }}\end{array}\right. xi​(g+1)={ui​(g+1),xi​(g),​ if f(ui​(g+1))⩽f(xi​(g)) otherwise ​

3. 算法代码 3.1 伪代码

在这里插入图片描述

3.2 matlab 4. 参数控制1

    DE算法主要的控制参数包括:种群规模(NP)、缩放因子(F)和交叉概率(CR)。

4.1 参数说明

NP主要反映算法中种群信息量的大小,NP值越大种群信息包含的越丰富,但是带来的后果就是计算量变大,不利于求解。反之,使种群多样性受到限制,不利于算法求得全局最优解,甚至会导致搜索停滞。

CR主要反映的是在交叉的过程中,子代与父代、中间变异体之间交换信息量的大小程度。CR的值越大,信息量交换的程度越大。反之,如果CR的值偏小,将会使种群的多样性快速减小,不利于全局寻优。

相对于CR,F对算法性能的影响更大,F主要影响算法的全局寻优能力。F越小,算法对局部的搜索能力更好,F越大算法越能跳出局部极小点,但是收敛速度会变慢。此外,F还影响种群的多样性

4.2 参数选择 M:一般介于5n到10n之间,但不能少于4,否则变异算则无法进行F:一般在[0,2],通常取0.5CR:[0,1],通常取0.3.CR越大,收敛速度越快,但易发生早熟现象。 5. 改进方法1

基本DE算法在求解的过程中,随着进化代数的增加,会使种群的多样性变小,过早的收敛到局部极小点,或者致使算法停滞,这对依靠种群差异来进行进化的算法来说无疑是致命的,使算法的性能在进化的过程中变差。

为了解决基本DE算法的上述缺陷,针对DE算法的特点,目前主要的改进方法是针对进化模式和控制参数的优化,还有一些改进方法是将DE算法与其他一些智能算法进行结合仲用。

5.1 自适应变异算子

    为了避免早熟,增加自适应变异算子。算子算法如下: λ = e 1 − G m G m + 1 − G F = F 0 ⋅ 2 2 \begin{array}{l}{\lambda=e^{1-\frac{G_{m}}{G_{m}+1-G}}} \\ {F=F_{0} \cdot 2^{2}}\end{array} λ=e1−Gm​+1−GGm​​F=F0​⋅22​ w h e r e where where, F 0 F_{0} F0​为变异算子; G m G_{m} Gm​为最大进化代数; G G G为当前进化代数。

    算法开始时,自适应算子 F = F 0 F= F_{0} F=F0​~ 2 F 0 2F_{0} 2F0​。具有较大值时,初期保持个体多样性,避免早熟,随着算法进度的不断变化,变异算子的值逐步降低,后期变异率接近 F 0 F_{0} F0​,保留优良信息,避免最优解遭到破坏,增加搜索到全局最优解的概率。

https://baike.baidu.com/item/%E5%B7%AE%E5%88%86%E8%BF%9B%E5%8C%96%E7%AE%97%E6%B3%95/10052475?fr=aladdin ↩︎ ↩︎



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3